/* 网格图模型

* 本题:
    建图：建立源点 s 和汇点 t，
    对于方格上的每个点来说其上的值只能取一次，即对点有限制，需要拆点，
    即将方格上的每个点拆分为入点和出点，入点向出点连边，容量为 1，费用为点权，
    又由于一个点可以经过多次，即可能存在这样一种情况：再次经过该点，但没有权值，不妨再次从入点向出点连边，容量足够大，费用为 0，
    同时原方格中 点与点之间也需要连边，即每个点的出点需要向其下方和右方的点的入点连边，容量足够大，费用为 0，
    另外，源点向方格左上角的第一个点的入点连边，容量为 k，费用为 0，
        方格右下角的最后一个点的出点向 t 连边，容量为 k，费用为 0，
    最后求解从 s 到 t 的最大费用最大流即为所求
    点的编号id，入点2*id，出点2*id+1

    从入点像出点连权值分别为(1,w)和（INF,0)的边
*/

#define DEBUG
#pragma GCC optimize("O1,O2,O3,Ofast")
#pragma GCC optimize("no-stack-protector,unroll-loops,fast-math,inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,sse4,sse4.1,sse4.2,ssse3")

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5010, M = N*8, INF=0x3f3f3f3f;
int n, k, S, T;
int h[N], e[M], c[M], w[M], ne[M], idx;
int q[N], pre[N], incf[N], d[N];
bool st[N];

//返回每个点的下标 t: 0为入点 1为出点
#define get(x,y,t) (((x)*n+y)*2+t)

void AddEdge(int a, int b, int cc, int ww)
{
    e[idx]=b, c[idx]=cc, w[idx]=ww, ne[idx]=h[a], h[a]=idx++;
    e[idx]=a, c[idx]=0, w[idx]=-ww, ne[idx]=h[b], h[b]=idx++;
}

bool spfa()
{
    memset(d, -0x3f, sizeof d);
    memset(incf, 0, sizeof incf);
    int hh=0, tt=0;
    q[tt++]=S, d[S]=0, incf[S]=INF;
    while(hh!=tt)
    {
        int u=q[hh++];
        if(hh==N) hh=0;
        st[u]=false;
        for(int i=h[u]; ~i; i=ne[i])
        {
            int v=e[i];
            if(c[i] && d[v]<d[u]+w[i])
            {
                d[v]=d[u]+w[i];
                pre[v]=i;
                incf[v]=min(incf[u], c[i]);
                if(!st[v])
                {
                    q[tt++]=v;
                    if(tt==N) tt=0;
                    st[v]=true;
                }
            }
        }
    }
    return incf[T]>0;
}

int EK()
{
    int cost = 0;
    while(spfa())
    {
        cost += incf[T]*d[T];
        for(int i=T; i!=S; i=e[pre[i]^1])
        {
            c[pre[i]]-=incf[T]; c[pre[i]^1]+=incf[T];
        }
    }
    return cost;
}


signed main()
{
    #ifdef DEBUG
        freopen("./in.txt","r",stdin);
    #else
        ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    #endif

    memset(h, -1, sizeof h);

    cin >> n >> k;
    S = 2*n*n, T=S+1; //每个点拆成两个点
    AddEdge(S, get(0,0,0), k, 0); //虚拟源点
    AddEdge(get(n-1,n-1,1), T, k, 0); //虚拟汇点

    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
        {
            int c; cin >> c;
            AddEdge(get(i,j,0), get(i,j,1), 1, c); //入点->出点 取当前数
            AddEdge(get(i,j,0), get(i,j,1), INF, 0); //入点->出点 不取当前数(每个数只能取一次)
            if(i+1<n) AddEdge(get(i,j,1), get(i+1,j,0), INF, 0); //向下走
            if(j+1<n) AddEdge(get(i,j,1), get(i,j+1,0), INF, 0); //向右走
        }

    printf("%d\n", EK());
    return 0;
}